package th.retrofit.lib;

import java.util.Scanner;

import javax.xml.soap.Node;

public class NodeSolution {

    /**
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
     * 两两交换链表中的节点
     * 添加虚拟节点的方式：
     * 原始链表: 5 -> 4 -> 3 -> 2 -> 1
     * 交换后的链表： 4 -> 5 -> 2 -> 3 -> 1
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode temp = dummyNode;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = node1.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyNode.next;
    }

    /**
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
     * 两两交换链表中的节点
     * 原始链表: 5 -> 4 -> 3 -> 2 -> 1
     * 交换后的链表： 4 -> 5 -> 2 -> 3 -> 1
     */
    public ListNode swapPairs1(ListNode head) {
        ListNode newHead = head;
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (newHead == head) {
                newHead = cur.next;
            }
            ListNode next = cur.next;
            ListNode temp = next.next;
            next.next = cur;
            cur.next = null;
            if (pre != null) {
                pre.next = next;
            }
            pre = cur;
            cur = temp;
        }
        if (cur != null && pre != null) {
            pre.next = cur;
        }
        return newHead;
    }

    /**
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
     * 两两交换链表中的节点
     * 原始链表: 5 -> 4 -> 3 -> 2 -> 1
     * 交换后的链表： 4 -> 5 -> 2 -> 3 -> 1
     */
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode next = head.next;
        ListNode temp = swapPairs2(next.next);
        next.next = head;
        head.next = temp;
        return next;
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode next = head.next;
        ListNode reversedHead = reverse(next);
        next.next = head;
        head.next = null;
        return reversedHead;
    }

    /**
     * K 个一组翻转链表
     * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
     * 递归解法：
     * 初始链表: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
     * 当 k=4 时
     * 交换后的链表：6 -> 7 -> 8 -> 9 -> 2 -> 3 -> 4 -> 5 -> 1
     *
     * @param head 原始链表
     * @param k    k个为一组
     * @return 翻转后的链表
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        if (cur == null || k == 0) return head;
        for (int i = 0; i < k - 1; i++) {
            cur = cur.next;
            if (cur == null) {
                return head;
            }
        }
        ListNode reversedHead = reverseKGroup(cur.next, k);
        cur.next = null;
        ListNode newHead = reverse(head);
        head.next = reversedHead;
        return newHead;
    }

    /**
     * K 个一组翻转链表
     * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
     * 递归解法：
     * 初始链表: 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
     * 当 k=4 时
     * 交换后的链表：6 -> 7 -> 8 -> 9 -> 2 -> 3 -> 4 -> 5 -> 1
     *
     * @param head 原始链表
     * @param k    k个为一组
     * @return 翻转后的链表
     */
    public ListNode reverseKGroup1(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head;
        ListNode temp = dummy;
        while (cur != null) {
            ListNode tail = cur;
            for (int i = 0; i < k - 1; i++) {
                tail = tail.next;
                if (tail == null) {
                    temp.next = cur;
                    return dummy.next;
                }
            }
            ListNode childHead = cur;
            cur = tail.next;
            tail.next = null;
            temp.next = reverse(childHead);
            temp = childHead;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(5, new ListNode(4, new ListNode(3,
                new ListNode(2, new ListNode(1)))));
        ListNode other = new ListNode(8, new ListNode(7, new ListNode(6, head)));
        ListNode another = new ListNode(9, other);
//        System.out.println(new NodeSolution().reverse(head));
//        System.out.println(new NodeSolution().swapPairs(head));
//        System.out.println(another);
        System.out.println(new NodeSolution().reverseKGroup1(another, 4));
    }

}
